Every packet switch or router in a communications network has means to buffer packets, typically realized by a traffic manager (TM) that queues and dequeues the packets from external memory (typically realized with dynamic random access memory, DRAM) based on credits issued by a scheduler. Packet buffering is required either because the forwarding port at which the packet is destined is currently not available or congested, or because the scheduler is currently scheduling other egress ports. To perform packet buffering, the TM needs to implement a memory controller that is managing the DRAM devices in terms of timing and bank access management.
DRAMs are large arrays of memory capacitors that consist of columns and rows in which the information is stored. In order to access one location in the memory array the particular row is selected through a row access select (RAS) pin and related circuitry. Internally, the DRAM connects that row to a chain of so-called sense amplifiers that access certain memory locations, i.e. particular columns or all columns, in that row. As used herein, the word “access” means a write or read process to and from an external memory, or to and from the TM device or any other device involved in a packet buffering operation. Due to the specific operations of DRAMs, a latency is associated with accessing the content in any row of that memory array. This access latency is called the “row-cycle time” (tRC), sometimes also referred to as “RAS cycle time” or “random cycle time”. For standard synchronous DRAM (SDRAM), the tRC time is on the order of 50 nanoseconds (ns). Special type of DRAM such as fast-cycle RAM (FCRAM) or reduced-latency DRAM (RLDRAM) have tRC times on the order of 25 ns to 15 ns.
DRAMs typically have multiple “banks” of these memory arrays that operate simultaneously. For example, standard double-data rate (DDR) SDRAM devices have four banks while large DDR2 or DDR3 SDRAM devices or RLDRAM devices have eight memory banks. Having more banks available means that memory throughput can be increased by accessing data that is distributed over multiple banks. However, for any given bank, there is still a latency associated with the tRC wait time, during which the memory content stored in any row or column of that particular bank is not accessible. This can have a dramatic impact on access delay times and on overall memory throughput. Therefore, intelligent memory controllers are used to minimize bank access conflicts and increase efficiency, which is measured in packet throughput per second.
Memory controllers in use today are based on linked lists in which a packet to be written or read, to and from the memory, is divided into fragments or bursts, which are then stored in random locations (e.g., banks, rows or columns) of the memory. Whenever a packet is read out, the corresponding memory locations have to be released in order to create additional space, for example, to accommodate another linked list and data bursts. Since linked list management is rather complex and prone to failures, e.g., corruption of one pointer destroys the whole linked list, and it is challenging to achieve high memory efficiencies, there is an ongoing need for improved memory controller for use in high-speed packet applications.
The typical approach for realizing efficient memory controllers is to work with packet fragments that are stored and spread over various memory banks, hence avoiding bank access conflicts due to tRC wait times. That means for each packet, a sequence of “nodes” is created where each node contains fragment information such as memory address, length, or other identifiers, and typically, one pointer linking this node to the next node. In order to access one packet in the memory, the complete list of nodes (“linked list”) needs to be processed. This is potentially error-prone because corruption of one pointer may corrupt the whole list. Furthermore, different packets are often sharing fragments and/or linked lists, for example, one common linked list for all packets stored in the same scheduling queue, so that management and correct maintenance of the linked list is of highest priority in these linked list memory controller architectures.